package a00_LeetCode.Set;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author quan
 * @Description 复制带随机指针的链表[巧用Map的映射关系]
 * @Date 2023/4/5 21:14
 */
public class Num138_copyRandomList {
    public Node copyRandomList(Node head) {
        //遍历原链表，构建新链表，保存在Map接口中
        Map<Node,Node> map = new HashMap<>();//Map接口的两个Node分别表示原链表的节点和新链表对应位置的节点
        Node temp = head;
        while (temp != null){
            Node node = new Node(temp.val);//每走到一个节点，创建一个新节点
            map.put(temp,node);//将原节点和对应位置的新节点存储到map中
            temp = temp.next;
        }
        //此时map中已经保存了原链表和新链表两两对应位置的节点
        temp = head;//重新从链表头部开始，建立节点的next引用以及random关系
        while (temp!=null){
            map.get(temp).next = map.get(temp.next);//当前节点的对应位置的新节点的next = 原先节点的Next指向
            map.get(temp).random = map.get(temp.random);//random引用
            temp = temp.next;
        }
        return map.get(head);//通过原链表的头结点找到新链表的头结点
    }
}
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}